package org.lintcode_Pattern;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/**
 * @Auther: qingle
 * @Date: 2024/8/20-22:49
 * @Description:
 * 使用条件
 * 1. 拓扑排序(100%)
 * 2. 出现连通块的关键词(100%)
 * 3. 分层遍历(100%)
 * 4. 简单图最短路径(100%)
 * 5. 给定一个变换规则，从初始状态变到终止状态最少几步(100%)
 * 复杂度
 * • 时间复杂度：O(n + m)
 * ￮ n 是点数, m 是边数
 * • 空间复杂度：O(n)
 * 炼码例题
 * • LintCode 974. 01 矩阵(分层遍历)
 * • LintCode 431. 找无向图的连通块
 * • LintCode 127. 拓扑排序
 * @version: 1.0
 */
public class A6宽度优先搜索BFS {

	class Node {
		// 假设 Node 类有 getNeighbors 方法可以返回当前节点的所有邻居节点
		public List<Node> getNeighbors() {
			// 实现略
			return new ArrayList<>();
		}

		@Override
		public String toString() {
			// 为了输出方便，重写 toString 方法
			return "Node{" +
				"value=" + value +
				'}';
		}

		// 可以添加一个标识符，比如 value，以区分不同的 Node
		private final int value;
		public Node(int value) {
			this.value = value;
		}

		// 可能还需要覆盖 equals 和 hashCode 方法，以便在 HashMap 中使用
		// 实现略
	}

	public static class TopologicalSort {

		// 拓扑排序
		public List<Node> topologicalSort(List<Node> nodes) {
			// 统计所有点的入度信息，放入 hashmap 里
			Map<Node, Integer> indegrees = getIndegrees(nodes);

			// 将所有入度为 0 的点放到队列中
			Queue<Node> queue = new ArrayDeque<>();
			for (Node node : nodes) {
				if (indegrees.get(node) == 0) {
					queue.offer(node);
				}
			}

			List<Node> topoOrder = new ArrayList<>();
			while (!queue.isEmpty()) {
				Node node = queue.poll();
				topoOrder.add(node);
				for (Node neighbor : node.getNeighbors()) {
					// 入度减一
					indegrees.put(neighbor, indegrees.get(neighbor) - 1);
					// 入度减到 0 说明不再依赖任何点，可以被放到队列（拓扑序）里了
					if (indegrees.get(neighbor) == 0) {
						queue.offer(neighbor);
					}
				}
			}

			// 如果 queue 是空的时候，图中还有点没有被挖出来，说明存在环
			// 有环就没有拓扑序
			if (topoOrder.size() != nodes.size()) {
				// 处理没有拓扑序的情况，这里可以是返回一个空列表或者抛出异常
				return new ArrayList<>();
			}

			return topoOrder;
		}

		private Map<Node, Integer> getIndegrees(List<Node> nodes) {
			Map<Node, Integer> indegrees = new HashMap<>();
			for (Node node : nodes) {
				indegrees.put(node, 0);
			}
			for (Node node : nodes) {
				for (Node neighbor : node.getNeighbors()) {
					indegrees.put(neighbor, indegrees.getOrDefault(neighbor, 0) + 1);
				}
			}
			return indegrees;
		}

		// 示例主函数，演示如何使用 topologicalSort 方法
		public static void main(String[] args) {
			// 假设创建了一些 Node 对象并构建了依赖关系
			List<Node> nodes = new ArrayList<>();
			// 填充 nodes 列表和构建图的代码略

			TopologicalSort topoSort = new TopologicalSort();
			List<Node> sortedNodes = topoSort.topologicalSort(nodes);
			System.out.println(sortedNodes); // 输出拓扑排序结果
		}
	}
}
